package may;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-5-15 21:52
 * @description：
 * @modified By：
 * @version:
 */
public class May15 {
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/climbing-stairs/ 爬楼梯
     * create time: 2020-5-15 21:52
     * @params [n]
     * @return int
     */
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] list = new int[n+1];
        list[1] = 1;
        list[2] = 2;
        for (int i = 3; i < list.length; i++) {
            list[i] = list[i-1]+list[i+2];
        }
        return list[n];
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/the-masseuse-lcci/ 按摩师 和 4月的一个小偷类似
     * create time: 2020-5-15 21:58
     * @params [nums]
     * @return int
     */
    public int massage(int[] nums) {
        int preMax = 0;
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            int a = max;
            max = Math.max(preMax+nums[i],max);
            preMax = a;
        }
        return max;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/contiguous-sequence-lcci/ 连续数列最大和
     * 总体思想就是
     * 1. 从0开始一步步往右边推进
     * 2. 当前的sum < 0 并且 当前位置的值比sum大 就sum = 当前位置的值
     * 3. 每回记录下最大值
     * create time: 2020-5-15 22:03
     * @params [nums]
     * @return int
     */
    public static int maxSubArray() {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        if(nums.length==0){
            return 0;
        }
        int right = 0;
        int sum = 0;
        int max = nums[0];
        for (;right < nums.length; right++) {
            if(sum<0){
                if(sum<nums[right]){
                    sum = nums[right]; //可能会越界
                    max = Math.max(sum,max);
                    continue;
                }

            }
            sum = sum+nums[right];
            max = Math.max(sum,max);
        }
        return max;
    }

    public static void main(String[] args) {
        maxSubArray();
    }
}
